package P150;

import java.util.*;

public class P57 {
    private static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public static ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) {
            return head;
        }

        ListNode virtual = new ListNode();
        virtual.next = head;

        int index = 0;
        ListNode pre = null;
        ListNode node = virtual;
        while (index <= left) {
            if (index + 1 == left) {
                pre = node;
            }
            node = node.next;
            ++index;
        }

        ListNode cur = pre.next;
        for (int i = 0; i < right - left; i++) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }

        return virtual.next;
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1) {
            return head;
        }
        Deque<Deque<ListNode>> stack = new LinkedList<>();
        Deque<ListNode> element = new LinkedList<>();
        ListNode node = head;
        while (node != null) {
            ListNode temp = node.next;
            node.next = null;
            element.addLast(node);
            node = temp;
            if (element.size() == k) {
                stack.addLast(element);
                element = new LinkedList<>();
            }
        }

        if (!element.isEmpty()) {
            stack.addLast(element);
        }

        // 虚拟节点
        ListNode v = new ListNode();
        ListNode cur = v;
        while (!stack.isEmpty()) {
            Deque<ListNode> listNodes = stack.pollFirst();
            if (listNodes.size() == k) {
                while (!listNodes.isEmpty()) {
                    cur.next = listNodes.pollLast();
                    cur = cur.next;
                }
            } else {
                while (!listNodes.isEmpty()) {
                    cur.next = listNodes.pollFirst();
                    cur = cur.next;
                }
            }
        }

        return v.next;
    }


    public static ListNode removeNthFromEnd(ListNode head, int n) {
        int left = 0, right = 1;
        ListNode v = new ListNode();
        v.next = head;
        ListNode leftNode = v;
        ListNode rightNode = head;
        while (rightNode != null) {
            if (rightNode.next == null) {
                leftNode.next = leftNode.next.next;
                return v.next;
            }
            rightNode = rightNode.next;
            ++right;
            if (right - left > n) {
                leftNode = leftNode.next;
                ++left;
            }
        }
        return v.next;
    }


    public static ListNode deleteDuplicates(ListNode head) {
        Map<Integer, Integer> map = new HashMap<>();
        ListNode v = new ListNode();
        v.next = head;
        // 计数
        while (head != null) {
            int key = head.val;
            int val = map.getOrDefault(key, 0) + 1;
            map.put(key, val);
            head = head.next;
        }
        // 删除
        ListNode pre = v;
        while (pre.next != null) {
            int key = pre.next.val;
            if (map.get(key) > 1) {
                pre.next = pre.next.next;
            } else {
                pre = pre.next;
            }
        }

        return v.next;
    }

    public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null) {
            return head;
        }
        int count = 1;
        ListNode lastNode = head;
        while (lastNode.next != null) {
            ++count;
            lastNode = lastNode.next;
        }

        k = k % count;
        if (k == 0) {
            return head;
        }

        ListNode left = head;
        int index = 1;
        while (index < count - k) {
            left = left.next;
            ++index;
        }

        lastNode.next = head;
        ListNode result = left.next;
        left.next = null;
        return result;
    }

    public static ListNode partition(ListNode head, int x) {
        if (head == null) {
            return head;
        }
        ListNode left = new ListNode();
        ListNode right = new ListNode();
        ListNode leftEnd = left;
        ListNode rightEnd = right;

        while (head != null) {
            if (head.val < x) {
                leftEnd.next = head;
                leftEnd = leftEnd.next;
            } else {
                rightEnd.next = head;
                rightEnd = rightEnd.next;
            }
            head = head.next;
        }
        leftEnd.next = right.next;
        rightEnd.next = null;
        return left.next;
    }



    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        ListNode node = partition(head, 3);
        while (node != null) {
            System.out.print(node.val);
            node = node.next;
        }
    }
}
